﻿#pragma once

#include <atomic>
#include <unordered_map>
#include <algorithm>
#include <mutex>
#include <iostream>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <thread>
#include <vector>

#ifdef _WIN32
	#include <windows.h>
#else 
	//Linux...
#endif


#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#elif
	//	Linux
#endif // _WIN64

// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}


//ThreadCache的最大容量
static const size_t MAX_BYTES_SIZE = 256 * 1024;

//freelists哈希桶的个数
static const size_t FREE_LIST_SIZE = 208;

//page Cache桶的个数（页数）
static const size_t PAGE_SIZE = 129;

//一页的大小是2的13次方，计算字节转页的偏移量
static const size_t PAGE_SHIFT = 13;


using std::cout;
using std::endl;


static void*& nextObj(void* obj) //快速获取自由链表下一跳地址
{
	return *(void**)obj;
	
}

class FreeList
{
public:
	void push(void* obj)
	{
		assert(obj);

		//头插
		nextObj(obj) = _freelist;
		_freelist = obj;
		++_size;
	}

	void* pop()
	{
		assert(_freelist);

		//头删
		void* obj = _freelist;
		_freelist = nextObj(obj);

		--_size;

		return obj;
	}

	void pushRange(void* start, void* end, size_t n)
	{
		nextObj(end) = _freelist;
		_freelist = start;
		_size += n;
	}

	void popRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);

		//遍历到 n - 1 的位置
		start = _freelist;
		end = start;
		for (size_t i = 0; i < n - 1; i++)
		{
			end = nextObj(end);
		}

		//pop
		_freelist = nextObj(end);
		nextObj(end) = nullptr;
		_size -= n; 
	}

	bool empty()
	{
		return _freelist == nullptr;
	}

	size_t& maxSize() // 可读可写
	{
		return _maxSize;
	}

	size_t size()
	{
		return _size;
	}

private:
	void* _freelist = nullptr; // 初始化
	size_t _maxSize = 1;
	size_t _size = 0;
};

// 管理对象的对齐和映射
class SizeClass
{
public:

// 整体控制在最多10%左右的内碎片浪费
// [1,128]					8byte对齐	    freelist[0,16)
// [128+1,1024]				16byte对齐	    freelist[16,72)
// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
	
	//这种写法的性能不够极致，下面实现参考库里面大佬的写法
	/*static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		size_t alignSize;	
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1)*alignNum;
		}
		else
		{
			alignSize = size;
		}

		return alignSize;
	}*/

	//采用位运算的方式，让性能更极致
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{ 
		return ((size) + alignNum - 1) & ~(alignNum - 1);
	}
	// 举两个样例 假设size为 1到8的情况，alignNum = 8
	// 1    +   7  =  8   00001000      &      11111000   = 8
	// 2              9   00001001                        = 8
	// ...                                                = 8
	// 8             15   00001111                        = 8


	// 假设size为 9到16的情况，alignNum = 8
	// 9    +   7  =  16   00010000      &      11111000   = 16
	// 10             17   00010001                        = 16
	// ...                                                 = 16
	// 16             23   00010111                        = 16


	//获取对齐数
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else //size > 256kb
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	//align_shift 表示是当前对齐数是2的多少次方
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	// 假设size为 9到16的情况，对齐数8是2的3次方，align_shift = 3
	//((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	// (((9 + (8) - 1) >> 3) - 1
	// 00000010 - 1 = 2 - 1 = 1


	// 计算映射的是哪一个自由链表的桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES_SIZE);

		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) 
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) 
		{
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024) 
		{
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) 
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}

		return -1;
	}

	// ⼀次从中⼼缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		if (size == 0)
			return 0;
		// [2, 512]，⼀次批量移动多少个对象的(慢启动)上限值
		// ⼩对象⼀次批量上限⾼
		// 大对象⼀次批量上限低
		int num = MAX_BYTES_SIZE / size;

		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;
		if (npage == 0) //低于16字节也至少获得一页的内存
			npage = 1;

		return npage;
	}
};

//管理多个连续页的大块内存跨度结构
struct Span 
{
	PAGE_ID _pageId = 0; //内存起始页的地址
	size_t _pageSize = 0;  // 页的数量

	//双链表结构
	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _objSize = 0; // 用于保存内存块的大小
	size_t _useCount = 0; // 记录小块内存分配各threadCache的个数
	void* _freeList = nullptr; // 管理切分好的小块内存

	bool _isUse = false;    //当前span 是否正在被使用，用于pageCache合并页时。
};

//带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* ret = _head->_next;
		Erase(ret);
		return ret;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		// prev -> newSpan -> pos
		Span* prev = pos->_prev;

		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		Span* next = pos->_next;
		Span* prev = pos->_prev;

		prev->_next = next;
		next->_prev = prev;

	}

	bool Empty()
	{
		return _head->_next == _head;
	}

private:
	Span* _head;
public:
	std::mutex _mtx; // 桶锁
};